package tree;

/**
 * 116. 填充每个节点的下一个右侧节点指针
 *
 * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点
 * 二叉树定义如下：
 * struct Node {
 *   int val;
 *   Node *left;
 *   Node *right;
 *   Node *next;
 * }
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 * 初始状态下，所有next 指针都被设置为 NULL。
 *
 * 限制：
 * 树中节点的数量在 [0, 2^12 - 1] 范围内
 * -1000 <= node.val <= 1000
 */

// 如通过递归语句在函数中的上一部分，则是自顶向下，如果是在后一部分，则是自下向上
public class PopulatingNextRightPointer_116 {
    // 自下向上，先从最下面的子树开始更新，慢慢的一步步向上更新
    public Node connect_error(Node root) {
        if (root == null) {
            return null;
        }

        Node left = connect_error(root.left);
        Node right = connect_error(root.right);

        if (left != null && right != null) {
            left.next = right;
            if (left.right != null) {
                left.right.next = right.left;
            }
        }

        return root;
    }

    // 自顶向下，从root节点开始更新，一步步更新其左右子树
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }

        Node left = root.left;
        Node right = root.right;

        // 完美二叉树，左子树不为空那么右子树也不为空
        // 从头结点开始更新，while循环将左子树的右节点和右子树的左节点连接起来
        while (left != null) {
            left.next = right;
            left = left.right;
            right = right.left;
        }

        // 头结点更新之后，再更新子节点
        connect(root.left);
        connect(root.right);
        return root;
    }
}
